Contents

1. 1. 题目：

• 八皇后的拓展
• 一样经典的题
• 回溯法解决

题目：

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

#include <cstdio>

int tot = 0, row, line[10], n;  	//line[row] = i;的意思是第row行的第i列

void Search(int row);

int main(){

    int a[11];
    for(n = 1; n <= 10; n++){
        tot = 0;
        Search(0);
        a[n] = tot;
    }
    while(scanf("%d", &n) != EOF && n){
        printf("%d\n", a[n]);
    }
    return 0;
}

void Search(int row)			//递归搜索可行解{

    int i, j;
    if(row == n)                        //当row=n时，说明每一行的皇后都不冲突，即为可行解
        tot++;
    else{
        for(i = 0; i < n; i++){
            bool istrue = true;
            line[row] = i;              //尝试把第row行的皇后放在i列上
            for(j = 0; j < row; j++){   //检验是否与前面已放好的皇后冲突
                if(line[row] == line[j] || line[row] - row == line[j] - j
                   || line[row] + row == line[j] + j){
                    istrue = false;
                    break;
                }
            }
            if(istrue)
                Search(row + 1);
        }
    }
}